package linklist;

import java.util.HashMap;

/**
 * @author kunkun
 * @className LeetCode_160
 * @Description 链表相交问题
 * @date 2025/3/12 10:23
 */
public class LeetCode_160 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        return solution1(headA,headB);
    }


    /**
    * @Description: 通过差值，寻找起始节点
    * @Author: kunkun
    * @Date:  2025/3/12 12:39
    * @Parameters:
    * @Return
    * @Throws
    */
    public ListNode solution1(ListNode headA, ListNode headB){

        //1. 遍历head1，head2
        ListNode head1 = headA,head2 = headB;
        int length1=0,length2=0;
        while(head1.next!=null){
            length1++;
            head1=head1.next;
        }
        length1++;
        while(head2.next!=null){
            length2++;
            head2=head2.next;
        }
        length2++;
        if (head1!=head2){
            return null;
        }


        //2. 根据长度寻找起始节点
        head1 = headA;
        head2 = headB;
        if (length1>length2){
            for (int i = 0; i < length1-length2; i++) {
                head1=head1.next;
            }
        }else{
            for (int i = 0; i < length2-length1; i++) {
                head2=head2.next;
            }
        }
        System.out.println("A"+head1.val);
        System.out.println("B"+head2.val);
        while(head1!=null){
            if (head1==head2){
                return head1;
            }
            head1=head1.next;
            head2=head2.next;
        }
        return null;

    }


}
